import java.util.Arrays;
import java.util.Stack;

public class MyStack {
    private int[] elem;
    private int usedSize;
    public MyStack(){
        this.elem = new int[5];
    }
    public void push(int val){
        //插入数据前需要先判断数组是否满了
        if (isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
    }
    public boolean isFull(){
//        if (usedSize == elem.length){
//            return true;
//        }
//        return false;
        return usedSize == elem.length;
    }
    public int pop(){
        //判断栈是否为空
        if (this.isEmpty()){
            throw new StackEmptyException("栈为空！");
        }
        //删除，使用usedSize--
        return elem[--usedSize];//先减再用，usedSize先变成usedSize-1，然后拿usedSize-1的值进行使用
    }
    public int peek(){
        if (this.isEmpty()){
            throw new StackEmptyException("栈为空！");
        }
        return elem[usedSize-1];
    }
    public boolean isEmpty(){
        if (usedSize == elem.length){
            return true;
        }
        return false;
    }
    //给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
    //请你计算该表达式。返回一个表示表达式值的整数
    public int evalRPN(String[] tokens){
        Stack<Integer> stack = new Stack<>();
        for (String s : tokens){
            if (!isOperate(s)){
                stack.push(Integer.parseInt(s));
            }
            else{
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch (s){
                    case "+":
                        stack.push(num2+num1);
                    break;
                    case "-":
                        stack.push(num2-num1);
                        break;
                    case "*":
                        stack.push(num2*num1);
                        break;
                    case "/":
                        stack.push(num2/num1);
                        break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isOperate(String s){
        if (s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    //有效字符串需满足：
    //左括号必须用相同类型的右括号闭合。
    //左括号必须以正确的顺序闭合。
    //每个右括号都有一个对应的相同类型的左括号。
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '('||ch == '['||ch == '{'){
                stack.push(ch);
            }else{
                if (stack.isEmpty()){
                    return false;
                }
                char tmp = stack.peek();
                if (ch == ')' && tmp == '('||ch == ']' && tmp == '['||ch == '}' && tmp == '{'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if (!stack.empty()){
            return false;
        }
        return true;
    }
    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
    // 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
    // 但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    public boolean IsPopOrder (int[] pushV, int[] popV) {
//        pushV int整型一维数组
//        popV int整型一维数组
//        return bool布尔型
        int j = 0;//用来遍历popV数组
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while(!stack.empty() && j < popV.length && stack.peek() == popV[j]){//一定要先判断栈是不是空栈，否则会报数组越界的错误
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

}
